package com.algorithm.base.greedy;

/**
 * 45. 跳跃游戏 II
 *
 * @author Amadeus
 * @date 2023/11/20
 */
public class Jump {

    public int jump(int[] nums) {
        int cover = 0;
        int result = 0;
        for (int i = 0; i <= cover; i++, result++) {
            cover = Math.max(nums[i] + i, cover);
            if (nums.length - 1 <= cover) {
                return i + 2;
            }
            int index = 0;
            for (int j = i + 1; j < cover; j++) {
                index = Math.max(index, j + nums[j]);
            }
            if (nums.length - 1 <= index) {
                return i + 1;
            }
        }
        return result;
    }

}
